package nextPermutation31;

import java.util.Arrays;

public class NextPermutation {

    //题目问题说明：例如nums = [1,2,3]，找出数组所组合的所有三位数比当前数序大的第一位数按照这个例子那就是[1,3,2]。
    //如果没有比当前数大的例如原nums = [3,2,1]则输出该数组从小到达排列

    //思路：需要找到数组中的两个数，前面的数比后面的数小，用两个指针去寻找，
    //i指针在前，j指针在后，由于要寻找最小的增量，所以，i要尽可能靠右，所以从后往前遍历

    //https://gitee.com/z_lamber/image-bed/raw/master/20210926173805.png
    public void nextPermutation(int[] nums) {
        //i 指针在前，从后往前遍历
        for(int i = nums.length-1; i>=0; i--){
            // j指针在后
            for(int j = nums.length-1; j>i; j--){
                if(nums[i] < nums[j]){
                    swap(nums,i,j);
                    Arrays.sort(nums,i+1,nums.length);
                    return;
                }
            }
        }
        //如果没有找到
        Arrays.sort(nums);
    }

    void swap(int[] a, int i, int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void main(String[] args) {
        int[] a = {1, 4, 5, 2};

        NextPermutation nextPermutation = new NextPermutation();
        nextPermutation.nextPermutation(a);

    }

}
